import javax.swing.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yinsh
 * Date: 2025-02-22
 * Time: 10:51
 */
public class SortTest {
    public void bubbleSort (int[] array) {
        for (int i = 0; i < array.length; i++) {
            boolean flag = false;
            //一趟冒泡排序比较n-1-i次【此处进行优化】
            for (int j = 0; j < array.length-1-i; j++) {
                //保证每一趟最大元素在最后
                if (array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            //一趟结束,若未进行交换则有序不再进行排序
            if (flag == false) {
                break;
            }
        }
    }

    public void choiceSort (int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            //找出每一趟最小元素的下标
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            //将最小元素的下标放在最前方
            swap(array,i,minIndex);
        }
    }

    public void insertSort (int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tamp = array[i];//取出tamp方便后续元素后移
            int j = i-1;
            for (; j >= 0 && array[j] > tamp;j--) {
                //如果当前元素比tamp大元素后移
                   array[j+1] = array[j];
            }
            //出循环后当前元素一定比tamp小
            array[j+1] = tamp;
        }
    }

    public void shellSort (int[] array) {
        int gap = array.length/2;
        while (gap > 0) {
            for (int i = 0; i < array.length; i+=2*gap) {
                int j = i + gap;
                insert(array,i,j);
            }
            gap /= 2;
        }
    }

    public void heapSort (int[] array) {
      createHeap(array);
      int end = array.length - 1;
      while (end > 0) {
          swap(array,0,end);
          end--;
          siftDown(array,0,end);
      }
    }

    public void mergeSort (int[] array) {
        partition (array,0,array.length-1);
    }
    public void qSort (int[] array) {
        qSortFunc(array,0,array.length-1);
    }


    private void qSortFunc(int[] array,int left,int right) {
        int pivot = division2(array,left,right);
        if (left >= right) return;
        qSortFunc(array,left,pivot);
        qSortFunc(array,pivot+1,right);
    }

    private int division (int[] array,int left,int right) {
        int tamp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tamp) {
                right--;
            }
            //出循环后right位置处值一定小于tamp
            array[left] = array[right];
            while (left < right && array[left] <= tamp) {
                left++;
            }
            //出循环后left位置处值一定大于tamp
            array[right] = array[left];
        }
        array[left] = tamp;
        return left;
    }

    private int division2 (int[] array,int left,int right) {
        //三数取中优化
        int mid = (left + right) / 2;
        //保证左边小于右边
        if (array[left] > array[right]) {
            swap(array,left,right);
        }
        //保证左小于中
        if (array[left] > array[mid]) {
            swap(array,left,mid);
        }
        //保证右大于左
        if (array[mid] > array[right]) {
            swap(array,mid,right);
        }
        int key = array[mid];


        while (left < right) {
            while (left<right && array[right] >= key) {
                right--;
            }
            while (left<right && array[left] <= key) {
                left++;
            }
            swap(array, left, right);
        }
        return left;
    }
    private void partition (int[] array,int left,int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        partition(array,left,mid);
        partition(array,mid+1,right);
        merge(array,left,right);
    }

    private void merge (int[] array,int left,int right) {
        int mid = (left + right) / 2;
        int[] tampArr = new int[right-left+1];
        int index = 0;
        int s1 = left;
        int s2 = mid + 1;
        while (s1<=mid && s2<=right) {
            if (array[s1] < array[s2]) {
                tampArr[index++] = array[s1++];
            } else if (array[s2] < array[s1]) {
                tampArr[index++] = array[s2++];
            }
        }
        while (s1 <= mid) {
            tampArr[index++] = array[s1++];
        }
        while (s2 <= right) {
            tampArr[index++] = array[s2++];
        }

        for (int i = 0; i < tampArr.length; i++) {
            array[i+left] = tampArr[i];
        }
    }


    private void createHeap (int[] array) {
        for (int parent = (array.length-2)/2;parent >= 0;parent--) {
            siftDown(array,parent,array.length-1);
        }
    }

    private void siftDown (int[] array,int parent,int end) {
        int child = 2 * parent + 1;
        while (child <= end) {
            if (child + 1 < end && array[child + 1] > array[child]) {
                child++;
            }
            if (child <= end && array[parent] < array[child]) {
                swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    private void insert (int[] array,int left,int right) {
        for (int i = 1; i < array.length; i++) {
            int tamp = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > tamp) {
                 array[j+1] = array[j];
                 j--;
            }
            //出循环此时j位置的值一定小于tamp
            array[j+1] = tamp;
        }
    }
    private void swap (int[] array,int x,int y) {
        int tamp = array[x];
        array[x] = array[y];
        array[y] = tamp;
    }
}
